package _02_greedy_algorithm;

import _02_greedy_algorithm.FractionalKnapsackProblem.Item;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: mornd
 * @dateTime: 2023/7/20 - 16:33
 * 0-1 背包问题
 * 使用贪心算法也不一定得到最优解，这种场景也不适用贪心算法
 */
public class KnapsackProblem {

    public static void main(String[] args) {
        /*
            1、n个物品都是固体
            2、现在要取走10g的物品
            3、每次可以不拿或者全拿(不能切割)，问最高价值是多少


            编号    重量(g)    价值(元)
            0       1         1_000_000   钻石一粒
            1       4         1600        黄金一块
            2       8         2400        红宝石一粒
            3       5         30          白银一块

        */

        Item[] items = new Item[]{
                new Item(0, 1, 1_000_000),
                new Item(1, 4, 1600),
                new Item(2, 8, 2400),
                new Item(3, 5, 30)
        };

        int price = select(items, 10);
        // 贪心算法得到的结果：price = 1001630     钻石一粒，黄金一块，白银一块
        System.out.println("price = " + price);
        // 最优解应该是 1_002_400   钻石一粒，红宝石一粒
    }

    private static int select(Item[] items, int total) {
        PriorityQueue<Item> queue = new PriorityQueue<>(
                Comparator.comparingInt(Item::unitValue).reversed()
        );
        queue.addAll(Arrays.stream(items).toList());
        int price = 0;

        while (total > 0) {
            Item poll = queue.poll();
            if (total >= poll.weight) {
                total -= poll.weight;
                price += poll.value;
            }
        }

        return price;
    }
}
